﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string.h>
#define MAXSIZE 10000//母串最大长度
#define SUBMAXSIZE 100 //子串最大长度 
using namespace std;
void My_Next(const char* p,int* next)
{
    int len = strlen(p);
    next[0] = -1;
    int j = 0, k = -1;
    //aba
    while (j < len)
    {
        if (k==-1)
        {
            k++;
            j++;
            next[j] = k;
        }
        else if (p[j] == p[k])
        {
            k++;
            j++;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}
int kmp(const char* p1, char* p2, int start,int *next)
{
    int i = start, j = 0;
    while (p1[i] && p2[j])
    {
        if (j == -1 || p1[i] == p2[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (!p2[j])
        return i - j;
    else
        return -1;
}
int main()
{
    char sStr[MAXSIZE],pStr[SUBMAXSIZE];
    int next[SUBMAXSIZE];
    cout << "输入母串";
    cin >> sStr;
    cout << "输入子串";
    cin >> pStr;
    My_Next(pStr,next);
    int index = kmp(sStr, pStr, 0, next);
    if (index == -1)
        cout << "子串不在母串中";
    else
        cout << "子串在母串中的位置是" << index + 1;
    return 0;
}

